#!/usr/env/bin python
# -*- coding: utf-8 -*-

# @Time    : 2020/4/4 13:09|13:09
# @Author  : yangdingyi
# @File    : 42. 接雨水
# @Software: PyCharm
from typing import List


class Solution:
    def trap(self, height: List[int]) -> int:
        ans = 0
        ll = len(height)
        if ll <= 0:
            return ans
        max_hs = []
        max_h = 0
        for i in range(ll):
            if height[i] > max_h:
                max_h = height[i]
                max_hs = [i]
            elif height[i] == max_h:
                max_hs.append(i)

        x = max_hs[0]
        y = max_hs[len(max_hs) - 1]
        h = 0
        for i in range(0, x):
            if height[i] < h:
                ans += h - height[i]
            elif height[i] > h:
                h = height[i]
        for i in range(x, y):
            ans += max_h - height[i]
        h = 0
        for i in range(ll-1, y, -1):
            if height[i] < h:
                ans += h - height[i]
            elif height[i] > h:
                h = height[i]
        return ans


solve = Solution()

hh = [0,1,0,2,1,0,1,3,2,1,2,1]
print(hh, solve.trap(hh))

